#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <functional>
#include <cstdio>
#include <cassert>
#include <list>
#include <map>
#include <string>
#include <ctime>
#include <cstring>
using namespace std;

// k is 1-indexed
template <typename T>
T getKth(const vector<T> &a, int la, int ra, const vector<T> &b, int lb, int rb, int k)
{
	if (ra < la)
		return b[lb + k - 1];
	if (rb < lb)
		return a[la + k - 1];

	int ma = (la + ra) / 2;
	int mb = (lb + rb) / 2;

	int len = ma - la + 1 + mb - lb + 1;
	if (len > k)
	{
		if (a[ma] > b[mb])
			return getKth(a, la, ma - 1, b, lb, rb, k);
		else
			return getKth(a, la, ra, b, lb, mb - 1, k);
	}
	else if (len <= k)
	{
		if (a[ma] <= b[mb])
			return getKth(a, ma + 1, ra, b, lb, rb, k - (ma - la + 1));
		else
			return getKth(a, la, ra, b, mb + 1, rb, k - (mb - lb + 1));
	}
}

void test()
{
	srand(time(0));
	for (int i = 0; i < 100; i++)
	{
		int s1 = rand() % 100;
		int s2 = rand() % 100;
		vector<int> v1, v2;
		v1.resize(s1);
		v2.resize(s2);
		for (int i = 0; i < v1.size(); i++)
			v1[i] = rand();
		for (int i = 0; i < v2.size(); i++)
			v2[i] = rand();
		sort(v1.begin(), v1.end());
		sort(v2.begin(), v2.end());
		vector<int> v3(v1.size() + v2.size());
		copy(v1.begin(), v1.end(), v3.begin());
		copy(v2.begin(), v2.end(), v3.begin() + v1.size());
		sort(v3.begin(), v3.end());
		for (int i = 0; i < v3.size(); i++)
		{
			int ans = getKth(v1, 0, v1.size() - 1, v2, 0, v2.size() - 1, i + 1);
			assert(ans == v3[i]);
			int zz = 3;
		}
	}
	for (int i = 0; i < 100; i++)
	{
		int s1 = rand() % 100;
		int s2 = rand() % 100;
		vector<int> v1, v2;
		v1.resize(s1);
		v2.resize(s2);
		for (int i = 0; i < v1.size(); i++)
			v1[i] = rand() % 30;
		for (int i = 0; i < v2.size(); i++)
			v2[i] = rand() % 30;
		sort(v1.begin(), v1.end());
		sort(v2.begin(), v2.end());
		vector<int> v3(v1.size() + v2.size());
		copy(v1.begin(), v1.end(), v3.begin());
		copy(v2.begin(), v2.end(), v3.begin() + v1.size());
		sort(v3.begin(), v3.end());
		for (int i = 0; i < v3.size(); i++)
		{
			int ans = getKth(v1, 0, v1.size() - 1, v2, 0, v2.size() - 1, i + 1);
			assert(ans == v3[i]);
			int zz = 3;
		}
	}
}


int main()
{
	for (int i = 0; i < 10; i++)
		test();
	system("pause");
	return 0;
}